#include <iostream>
#include "linkQueue.h"
using namespace std;

#define MaxSize 100
/// @brief 树节点
struct TreeNode
{
    int value;    // 节点中的数据元素
    bool isEmpty; // 节点是否为空
};

struct Elemtype
{
    int value;
};

/// @brief 二叉树的节点（链式存储）
typedef struct BiTNode
{
    Elemtype data;
    struct BiTNode *lchild, *rchild; // 左、右孩子节点
} BiTNode, *BiTree;

// /// @brief 二叉树的节点（链式存储）
// typedef struct BiTNode
// {
//     Elemtype data;
//     struct BiTNode *lchild, *rchild; // 左、右孩子节点
//     struct BiTNode *parent;          // 父节点指针，三叉链表，方便找父节点
// } BiTNode, *BiTree;

void visit(BiTree T)
{
    printf("%d", T->data);
}
/// @brief 先序遍历
/// @param T
void PreOrder(BiTree T)
{
    if (T != NULL)
    {
        visit(T);            // 访问根节点
        PreOrder(T->lchild); // 递归遍历左子树
        PreOrder(T->rchild); // 递归遍历右子树
    }
}

/// @brief 中序遍历
/// @param T
void InOrder(BiTree T)
{
    if (T != NULL)
    {
        InOrder(T->lchild); // 递归遍历左子树
        visit(T);           // 访问根节点
        InOrder(T->rchild); // 递归遍历右子树
    }
}

/// @brief 后序遍历
/// @param T
void PostOrder(BiTree T)
{
    if (T != NULL)
    {
        PostOrder(T->lchild); // 递归遍历左子树
        PostOrder(T->rchild); // 递归遍历右子树
        visit(T);             // 访问根节点
    }
}

/// @brief 求树的深度（应用）
/// @param T
/// @return
int treeDepth(BiTree T)
{
    if (T == NULL)
    {
        return 0;
    }
    else
    {
        int l = treeDepth(T->lchild);
        int r = treeDepth(T->rchild);
        // 树的深度=Max（左子树深度，右子树深度）+1
        return l > r ? l + 1 : r + 1;
    }
}

/// @brief 层序遍历
/// @param T
void LevelOrder(BiTree T)
{
    LinkQueue Q;
    InitQueue(Q);
    BiTree p;
    EnQueue(Q, T);
    isEmpty(Q);
    while(!isEmpty(Q))
    {
        DeQueue(Q, p);
        visit(p);
        if (p->lchild != NULL)
        {
            EnQueue(Q, p->lchild);
        }
        if (p->rchild != NULL)
        {
            EnQueue(Q, p->rchild);
        }
    }
}